import {
  IBinarySearchTreeKey,
  IBinarySearchTree,
  ITraversalCallBack,
  IInsertCallback,
  INode
} from "@/interface";
import {
  initConfig
} from "@/config";

function BinarySearchTree() {
  let id = 0;

  function resetNode(data: INode, node: INode) {
    const { offset, isLeft, isRoot, parent, top, level } = data;
    node.offset = offset;
    node.isLeft = isLeft;
    node.isRoot = isRoot;
    node.parent = parent;
    node.parentId = parent?.id;
    node.top = top;
    node.level = level;
    return node;
  }

  // @ts-ignore
  function Node(key: IBinarySearchTreeKey): INode {
    this.id = id++;
    this.parent = null;
    this.parentId = null;
    this.level = null;
    this.$el = null;
    this.left = null;
    this.key = key;
    this.right = null;
    this.isLeft = false;
    this.top = 0;
    this.offset = 0;
    this.isRoot = false;
    this.leftLine = initConfig.lineWidth;
    this.rightLine = initConfig.lineWidth;
    this.leftAngle = initConfig.lineAngle;
    this.rightAngle = -initConfig.lineAngle;
  }

  // 属性
  this.root = null;

  //方法
  // 插入数据: 对外给用户调用的方法
  BinarySearchTree.prototype.insert = function(
    key: IBinarySearchTreeKey,
    handler: IInsertCallback
  ) {
    // 1.根据key创建新节点
    // @ts-ignore
    const newNode: INode = new Node(key);

    // 2.判断根节点是否有值
    if (this.root) {
      this._insertNode(this.root, newNode, handler);
    } else {
      resetNode(handler(null), newNode);
      this.root = newNode;
    }
  };

  // 递归方法
  BinarySearchTree.prototype._insertNode = function(
    node: INode,
    newNode: INode,
    handler: IInsertCallback
  ) {
    // 向左或向右查找
    const key = newNode.key < node.key ? "left" : "right";
    if (node[key]) {
      this._insertNode(node[key], newNode, handler);
    } else {
      resetNode({ ...handler(node, key), parent: node }, newNode);
      node[key] = newNode;
    }
  };

  // 树的遍历
  // 1.先序遍历
  BinarySearchTree.prototype.preOrderTraversal = function(
    handler: ITraversalCallBack
  ) {
    this._preOrderTraversalNode(this.root, handler);
  };

  BinarySearchTree.prototype._preOrderTraversalNode = function(
    node: IBinarySearchTree,
    handler: ITraversalCallBack
  ) {
    if (node) {
      // 1.处理经过的节点
      handler(node.key);

      // 2.处理经过节点的左节点
      this._preOrderTraversalNode(node.left, handler);

      // 3.处理经过节点的右节点
      this._preOrderTraversalNode(node.right, handler);
    }
  };

  // 2.中序遍历
  BinarySearchTree.prototype.midOrderTraversal = function(
    handler: ITraversalCallBack
  ) {
    this._midOrderTraversalNode(this.root, handler);
  };

  BinarySearchTree.prototype._midOrderTraversalNode = function(
    node: IBinarySearchTree,
    handler: ITraversalCallBack
  ) {
    if (node) {
      // 1.处理经过节点的左子树
      this._midOrderTraversalNode(node.left, handler);
      // 2.处理经过的节点
      handler(node.key);
      // 3.处理经过节点的右子树
      this._midOrderTraversalNode(node.right, handler);
    }
  };

  // 3.后序遍历
  BinarySearchTree.prototype.postOrderTraversal = function(
    handler: ITraversalCallBack
  ) {
    this._postOrderTraversalNode(this.root, handler);
  };

  BinarySearchTree.prototype._postOrderTraversalNode = function(
    node: IBinarySearchTree,
    handler: ITraversalCallBack
  ) {
    if (node) {
      this._postOrderTraversalNode(node.left, handler);
      this._postOrderTraversalNode(node.right, handler);
      handler(node.key);
    }
  };

  // 获取最大值
  BinarySearchTree.prototype.max = function(
    handler: ITraversalCallBack
  ): number | "" {
    let node = this.root;
    if (node) {
      while (node.right) {
        handler(node.key);
        node = node.right;
      }
      handler(node.key);
      return node.key;
    }
    return "";
  };

  // 获取最小值
  BinarySearchTree.prototype.min = function(
    handler: ITraversalCallBack
  ): number | "" {
    let node = this.root;
    if (node) {
      while (node.left) {
        handler(node.key);
        node = node.left;
      }
      handler(node.key);
      return node.key;
    }
    return "";
  };

  // 搜索一个指定的key
  BinarySearchTree.prototype.search = function(
    key: IBinarySearchTreeKey,
    handler: ITraversalCallBack
  ) {
    this._searchNode(this.root, key, handler);
  };

  BinarySearchTree.prototype._searchNode = function(
    node: IBinarySearchTree,
    key: IBinarySearchTreeKey,
    handler: ITraversalCallBack
  ) {
    handler(node.key);
    if (key < node.key) {
      this._searchNode(node.left, key, handler);
    } else if (key > node.key) {
      this._searchNode(node.right, key, handler);
    }
  };

  // 删除节点
  BinarySearchTree.prototype.remove = function(
    key: IBinarySearchTreeKey,
    handler: ITraversalCallBack
  ): boolean {
    // 1.寻找要删除的节点
    // 1.1.定义变量, 保存一些信息
    let current = this.root;
    let parent: any = null;
    let isLeftChild = true;

    // 1.2开始寻找删除的节点
    while (current.key !== key) {
      handler(current.key);
      parent = current;
      if (key < current.key) {
        isLeftChild = true;
        current = current.left;
      } else {
        isLeftChild = false;
        current = current.right;
      }
      // 某些情况: 已经找到了最后的节点, 依然没有找到===key
      if (current === null) return false;
    }

    // 2.根据对应的情况删除节点 -> 找到了current.key === key
    // 2.1删除的节点是叶子节点(没有子节点)
    if (!current.left && !current.right) {
      // 要删除的是根节点
      if (current.key === this.root.key) {
        this.root = null;
      } else {
        isLeftChild ? (parent.left = null) : (parent.right = null);
      }
    }
    // 2.2删除的节点只有一个子节点
    else if (!current.left) {
      if (current.key === this.root.key) {
        this.root = current.right;
      } else {
        isLeftChild
          ? (parent.left = current.right)
          : (parent.right = current.right);
      }
    } else if (!current.right) {
      if (current.key === this.root.key) {
        this.root = current.left;
      } else {
        isLeftChild
          ? (parent.left = current.left)
          : (parent.right = current.left);
      }
    }
    // 2.3删除的节点有两个子节点
    else {
      // 1.获取后继节点
      const successor = this._getSuccessor(current);
      // 2.判断是否是根节点
      if (current.key === this.root.key) {
        this.root = successor;
      } else if (isLeftChild) {
        parent.left = successor;
      } else {
        parent.right = successor;
      }
      // 3.将删除节点的左子树 = current.left;
      successor.left = current.left;
    }
    return true;
  };

  // 找后继的方法
  BinarySearchTree.prototype._getSuccessor = function(
    delNode: IBinarySearchTree
  ): IBinarySearchTree {
    // 1.保存变量, 保存找到的后继
    let successor = delNode;
    let current = delNode.right;
    let successorParent = delNode;

    // 2.循环查找
    while (current) {
      successorParent = successor;
      successor = current;
      current = current.left;
    }

    // 3.判断找到的后继节点是否直接就是delNode的right节点
    if (successor.key !== delNode.right.key) {
      successorParent.left = successor.right;
      successor.right = delNode.right;
    }

    return successor;
  };

  // 清空二叉搜索树
  BinarySearchTree.prototype.clear = function(): void {
    this.root = null;
    id = 0;
  };

  // 寻找同一层的节点
  BinarySearchTree.prototype.getSiblingNodes = function(node: INode): Array<INode> {
    const sibling: Array<INode> = [];
    this._siblingNode(this.root, node, (node: INode) => sibling.push(node));
    return sibling;
  };

  BinarySearchTree.prototype._siblingNode = function(tree: INode, node: INode, handler: (node: INode) => void) {
    if (tree.level === node.level && tree.key !== node.key) {
      handler(tree);
    } else {
      tree.left && this._siblingNode(tree.left, node, handler);
      tree.right && this._siblingNode(tree.right, node, handler);
    }
  }

  // 获取根节点
  BinarySearchTree.prototype.getRoot = function(): INode | null {
    return this.root;
  }

  // 获取某个子节点是根节点的左子树还有右子树
  BinarySearchTree.prototype.getChildrenFlag = function(node: INode, parent: INode = this.root) : string {
    let type = "";
    this._childrenFlag(node, parent, (key: string) => {
      type = key;
    });
    return type;
  }

  BinarySearchTree.prototype._childrenFlag = function(node: INode, parent: INode, handler: (key: string) => void) {
    if (parent && node?.parent?.id === parent?.id) {
      // node就是parent节点下的第一个子节点, 所以只需要判断这个节点的isLeft就可以
      handler(node.isLeft ? "left" : "right");
      return true;
    }
    this._childrenFlag(node?.parent, parent, handler);
  }

  // 获取两节点的共同父节点
  BinarySearchTree.prototype.getParentEqual = function(node: INode, refer: INode): INode | null {
    let parentEqual: any = null;
    this._parentEqual(node, refer, (equalParent: INode) => {
      parentEqual = equalParent;
    });
    return parentEqual;
  }

  BinarySearchTree.prototype._parentEqual = function(node: INode, refer: INode, handler: (equalParent: INode) => void) {
    /* 两个节点肯定是在同一个层级, 否则他们不会走到这个方法 */
    // 1.如果有一个的父级是根节点, 就直接返回根节点
    if (node?.parent?.isRoot || refer?.parent?.isRoot) {
      handler(this.root);
      return true;
    }
    // 2.如果node的父级id 和 refer的父级id 相同 则返回这个父级
    if (node?.parent?.id === refer?.parent?.id) {
      handler(node.parent);
      return true;
    }
    this._parentEqual(node?.parent, refer?.parent, handler);
  }

  // 寻找父级的父级节点(爷爷节点)
  BinarySearchTree.prototype.searchGrandpaNode = function(node: INode) {
    // 如果当前节点不是根节点
    if (!node.isRoot) {
      // 如果当前节点有父节点且父节点为根节点, 则直接返回父节点
      if (node.parent && node.parent.isRoot) return node.parent;
      // 如果当前节点有父节点且父节点不为根节点
      if (node.parent && !node.parent.isRoot) {
        const parent = node.parent;
        // 如果父节点的父节点存在 则返回他
        if (parent.parent) return parent.parent;
        // 如果父节点的父节点不存在 则返回父节点
        if (!parent.parent) return parent;
      }
      if (!node.parent) return node;
    }
    return node;
  }

}

export { BinarySearchTree };
